#include <stdio.h>
#include <stdlib.h>

#define datatype int
#define MAXSIZE 100
//顺序栈类型说明
typedef struct seqStack
{
  datatype a[MAXSIZE];
  int top;
} SEQSTACK;
//typedef struct seqStack SEQSTACK;

//结点类型说明
typedef struct node
{
  datatype data;
  struct node *next;
} NODE;

//链栈类型说明
typedef struct linkStack
{
  NODE *top;
  int length;
} LINKSTACK;

//顺序栈的常用操作
SEQSTACK *init_seqstack();                    //顺序栈的初始化 ，建立一个空的顺序栈
void push_seqstack(SEQSTACK *ss, datatype x); //入栈操作，不成功输出提示语
datatype pop_seqstack(SEQSTACK *ss);          //出栈操作，成功返回出栈的元素，不成功输出提示语
datatype gettop_seqstack(SEQSTACK *ss);       //得到栈顶元素
int full_seqstack(SEQSTACK *ss);              //判断栈是否已满，返回0代表不满，非0代表已满
int empty_seqstack(SEQSTACK *ss);             //判断栈是否为空，返回0代表不空，非0代表为空
void print_seqstack(SEQSTACK *ss);            //输出栈中元素，从栈底开始到栈顶

//链栈的常用操作
LINKSTACK *init_linkstack();                    //链栈的初始化 ，建立一个空的链栈
void push_linkstack(LINKSTACK *ss, datatype x); //入栈操作，不成功输出提示语
datatype pop_linkstack(LINKSTACK *ss);          //出栈操作，成功返回出栈的元素，不成功输出提示语
datatype gettop_linkstack(LINKSTACK *ss);       //得到栈顶元素
//链栈不需要判断栈已满
int empty_linkstack(LINKSTACK *ss);  //判断栈是否为空，返回0代表不空，非0代表为空
void print_linkstack(LINKSTACK *ss); //输出栈中元素，从栈底开始到栈顶

int main(int argc, char *argv[])
{
  // SEQSTACK *ss;
  // int i;
  // datatype fanhui;

  // ss=init_seqstack();
  // for(i=0;i<10;i++)
  //     push_seqstack(ss,10*(i+1));
  // printf("入栈之后栈的长度为：%d，元素为：",ss->top);
  // print_seqstack(ss);

  // printf("栈顶元素为：%d\n",gettop_seqstack(ss));

  // fanhui=pop_seqstack(ss);
  // printf("出栈元素为：%d,之后栈的长度为：%d，元素为：",fanhui,ss->top);

  // print_seqstack(ss);

  LINKSTACK *ss;
  int i;
  datatype fanhui;

  ss = init_linkstack();

  for (i = 0; i < 10; i++)
    push_linkstack(ss, 10 * (i + 1));
  printf("入栈之后栈的长度为：%d，元素为：", ss->length);
  print_linkstack(ss);

  printf("栈顶元素为：%d\n", gettop_linkstack(ss));

  fanhui = pop_linkstack(ss);
  printf("出栈元素为：%d,之后栈的长度为：%d，元素为：", fanhui, ss->length);

  print_linkstack(ss);

  system("PAUSE");
  return 0;
}

//顺序栈的初始化 ，建立一个空的顺序栈
SEQSTACK *init_seqstack()
{
  SEQSTACK *seqStack;
  seqStack = (SEQSTACK *)malloc(sizeof(SEQSTACK));
  seqStack->top = 0;
  return seqStack;
}

//入栈操作，不成功输出提示语
void push_seqstack(SEQSTACK *ss, datatype x)
{
  if (full_seqstack(ss))
  {
    printf("栈已存满");
  }
  else
  {
    ss->a[ss->top] = x;
    ss->top++;
  }
}

//出栈操作，成功返回出栈的元素，不成功输出提示语
datatype pop_seqstack(SEQSTACK *ss)
{
  if (empty_seqstack(ss))
  {
    printf("此为空栈");
  }
  else
  {
    return ss->a[ss->top--];
  }
}

//得到栈顶元素
datatype gettop_seqstack(SEQSTACK *ss)
{
  return ss->a[ss->top - 1];
}

/*判断栈是否已满，返回值为0代表不满，为非0代表为满*/
int full_seqstack(SEQSTACK *ss)
{
  if (ss->top >= MAXSIZE)
    return 1;
  return 0;
}

/*判断栈是否为空，返回值为0代表不空，为非0代表为空*/
int empty_seqstack(SEQSTACK *ss)
{
  if (ss->top == 0)
    return 1;
  return 0;
}

//输出栈中元素，从栈底开始到栈顶
void print_seqstack(SEQSTACK *ss)
{
  int i;
  for (i = 0; i < ss->top; i--)
    printf("%5d", ss->a[i]);
  printf("\n");
}

//链栈的初始化 ，建立一个空的链栈
LINKSTACK *init_linkstack()
{
  LINKSTACK *linkStack;
  linkStack = (LINKSTACK *)malloc(sizeof(LINKSTACK));
  NODE *node = (NODE *)malloc(sizeof(NODE));
  node->next = NULL;
  linkStack->top = node;
  linkStack->length = 0;
  return linkStack;
}

//入栈操作，不成功输出提示语
void push_linkstack(LINKSTACK *ss, datatype x)
{
  NODE *node = (NODE *)malloc(sizeof(NODE));
  node->data = x;
  node->next = ss->top->next;
  ss->top->next = node;
  ss->length++;
}

//出栈操作，成功返回出栈的元素，不成功输出提示语
datatype pop_linkstack(LINKSTACK *ss)
{
  if (empty_linkstack(ss))
  {
    printf("此为空栈");
  }
  else
  {
    int i;
    NODE *node = ss->top->next;
    i = node->data;
    ss->top->next = node->next;
    free(node);
    ss->length--;
    return i;
  }
}

//得到栈顶元素
datatype gettop_linkstack(LINKSTACK *ss)
{
  return ss->top->next->data;
}

//判断栈是否为空，返回0代表不空，非0代表为空
int empty_linkstack(LINKSTACK *ss)
{
  NODE *node = ss->top->next;
  if (node == NULL)
  {
    return 1;
  }
  else
  {
    return 0;
  }
}

//输出栈中元素，从栈底开始到栈顶
void print_linkstack(LINKSTACK *ss)
{
  NODE *node = ss->top->next;
  while (node!= NULL)
  {
    printf("%5d", node->data);
    node = node->next;
  }
  printf("\n");
}
